The existence of strongly polynomial algorithm for linear programming (LP)\nhas been widely sought after for decades. Recently, a new approach called\nGravity Sliding algorithm [1] has emerged. It is a gradient descending method\nwhereby the descending trajectory slides along the inner surfaces of a polyhedron\nuntil it reaches the optimal point. In R3, a water droplet pulled by gravitational\nforce traces the shortest path to descend to the lowest point. As the\nGravity Sliding algorithm emulates the water droplet trajectory, it exhibits\nstrongly polynomial behavior in R3. We believe that it could be a strongly polynomial\nalgorithm for linear programming in Rn too. In fact, our algorithm\ncan solve the Klee-Minty deformed cube problem in only two iterations, irrespective\nof the dimension of the cube. The core of gravity sliding algorithm\nis how to calculate the projection of the gravity vector g onto the intersection\nof a group of facets, which is disclosed in the same paper [1]. In this paper, we\nintroduce a more efficient method to compute the gradient projections on\ncomplementary facets, and rename it the Sliding Gradient algorithm under\nthe new projection calculation.
Loading....